/**
 * LeetCode122:路径总和
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，使这条路径上所有节点值的和等于目标和
 */

function TreeNode(val){
    this.val = val;
    this.left = this.right = null;
}

/**
 * @description 按照深度优先遍历，记录当前路径的节点值的和，在叶子节点处进行判断
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function (root,sum){
    if (!root) { return false;}
    let flag = false;
    const dfs = (n, val) => {
        if (!n.left && !n.right && sum === val){
            flag = true;
        }
        if (n.left) dfs(n.left,val + n.val);
        if (n.right) dfs(n.right, val + n.val);
    }
    dfs(root, root.val);
    return flag;
};

//时间复杂度：O(n)
//空间复杂度：最坏情况O(n)，最好情况O(log n)